package javase.arithmetic;

import org.junit.Test;

import java.util.Arrays;

/**
 * 快速排序
 * User: Realfighter
 * Date: 2015/6/16
 * Time: 10:20
 */
public class QuickSort {

    //    int[] array = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
    int[] array = {20, 40, 32, 67, 40, 20, 89, 300, 400, 15};

    @Test
    public void testQuickSort() {
        quickSort(0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public void quickSort(int left, int right) {
        if (left > right) {
            return;
        }
        int temp = array[left];//基准数
        int i = left, j = right, t;
        while (i != j) {
            //先从右往左
            while (array[j] >= temp && i < j) {
                j--;
            }
            //再从左往右
            while (array[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
        //将基准数归位
        array[left] = array[i];
        array[i] = temp;
        quickSort(left, i - 1);
        quickSort(i + 1, right);
    }

    @Test
    public void testQuickSort2() {
        quickSort2(0, array.length - 1);
        System.out.print(array[0] + " ");
        for (int i = 1; i < array.length; i++) {
            if (array[i] != array[i - 1]) {
                System.out.print(array[i] + " ");
            }
        }
    }

    /**
     * 快速倒序
     *
     * @param left
     * @param right
     */
    public void quickSort2(int left, int right) {
        if (left > right) {
            return;
        }
        int temp = array[left];//基准数
        int i = left, j = right, t;
        while (i != j) {
            //先从右往左
            while (array[j] <= temp && i < j) {
                j--;
            }
            //再从左往右
            while (array[i] >= temp && i < j) {
                i++;
            }
            if (i < j) {
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
        //将基准数归位
        array[left] = array[i];
        array[i] = temp;
        quickSort2(left, i - 1);
        quickSort2(i + 1, right);
    }

}
